#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

namespace YX
{
    template<typename T>
    class UnionFindSet
    {
        public:
            UnionFindSet(const T* a,size_t n)
                :_v(n,-1)
            {
                for(size_t i=0;i<n;i++)
                {
                    _indexMap[a[i]]=i;
                }
            }
            
            int GetIndex(const T& sign)
            {   
                auto pos=_indexMap.find(sign);

                if(pos!=_indexMap.end())
                {
                    return _indexMap[sign];
                }
                
                exit(1);

            }

            int FindRootIndex(int pos)
            {

                int root=pos;

                while(_v[root]>=0)
                {
                    root=_v[root];
                }

                // 路径压缩
                while(_v[pos]>=0)
                {
                    int parent=_v[pos];
                    _v[pos]=root;
                    pos=parent;
                }

                return root;
            }

            bool Union(const T& x,const T& y)
            {
                int xi=GetIndex(x);
                int yi=GetIndex(y);

                int xRoot=FindRootIndex(xi);
                int yRoot=FindRootIndex(yi);

                if(xRoot==yRoot)
                    return false;

                // 小的往大的合
                if(abs(_v[xRoot])<abs(_v[yRoot]))
                {
                    std::swap(xRoot,yRoot);
                }

                _v[xRoot]+=_v[yRoot];
                _v[yRoot]=xRoot;
                
                return true;
            }

            bool InSet(const T& x,const T& y)
            {
                int xi=GetIndex(x);
                int yi=GetIndex(y);

                int xRoot=FindRootIndex(xi);
                int yRoot=FindRootIndex(yi);

                return xRoot==yRoot;
            }

            size_t SetSize()
            {
                size_t size=0;
                for(size_t i=0;i<_v.size();i++)
                {
                    if(_v[i]<0)
                    {
                        size++;
                    }
                }
                return size;
            }

            void Print()
            {
                for(size_t i=0;i<_v.size();i++)
                {
                    cout<<i<<":"<<_v[i]<<endl;
                }
            }

        private:
            vector<int> _v;
            map<T,int> _indexMap;
    };

    void TestUnionFindSet()
    {
        string strArr[]={"A","B","C","D","E","F","G","H","I","J","k"};

        UnionFindSet<string> ufs(strArr,sizeof(strArr)/sizeof(strArr[0]));
        
        ufs.Union("A","B");
        ufs.Union("D","E");
        ufs.Union("G","I");
        ufs.Union("A","J");
        ufs.Union("B","E");
        ufs.Union("A","A");
        ufs.Print();
        cout<<"SetSize:"<<ufs.SetSize()<<endl;
        cout<<ufs.InSet("A","G")<<endl;
    }

};
